package com.springboot.demo.sort;

/**
 * 归并排序，稳定
 *
 * <p>
 * 算法思想：
 * <p>
 * 速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。
 * <p>
 * 1、选择相邻两个数组成一个有序序列。
 * <p>
 * 2、选择相邻的两个有序序列组成一个有序序列。
 * <p>
 * 3、重复第二步，直到全部组成一个有序序列。
 *
 * 时间复杂度：o(nlogn)
 *
 * @author supu
 * @date 2019-12-12 17:14
 **/
public class MergeSort {
    public static void mergeSort(int[] a, int low, int high) {
        if (low < high) {
            // 防止溢出，(high + low) / 2 这种写法有溢出的漏洞
            int mid = low + (high - low) / 2;
            // 或者使用无符号右移方式
//            int mid = (high + low) >>> 2;
            // 左边
            mergeSort(a, low, mid);
            // 右边
            mergeSort(a, mid + 1, high);
            // 左右边数据排序后合并
            sortMerge(a, low, mid, high);
        }
    }

    private static void sortMerge(int[] a, int low, int mid, int high) {
        // 临时存放排序后的数据
        int[] temp = new int[high - low + 1];
        // 临时数组temp存放数的位置
        int index = 0;
        // 左半边指针
        int i = low;
        // 右半边指针
        int j = mid + 1;
        while (i <= mid && j <= high) {
            if (a[i] >= a[j]) {
                // temp 存放右边的较小值
                temp[index++] = a[j++];
            } else {
                // temp 存放左边的较小值
                temp[index++] = a[i++];
            }
        }

        while (i <= mid) {
            // 左边剩余的数据
            temp[index++] = a[i++];
        }

        while (j <= high) {
            // 右边剩余的数据
            temp[index++] = a[j++];
        }

        for (int x = 0; x < temp.length; x++) {
            // 排好序的数组赋值给原数组a
            a[low + x] = temp[x];
        }
    }
}
